class TestLabyrint{
	// Listing 10.1 og 10.2 i læreboka
	// Opprettar labyrint og prøver å gå gjennom
	// Eksempel på rekursiv metode (på vanskeleg problem)
	//
	public static void main(String[] a){
		Labyrint lab1 = new Labyrint();
		System.out.println(lab1);
		if(lab1.gåGjennom(0,0))
			System.out.println("Kom gjennom denne labyrinten slik:");
		else
			System.out.println("Ingen stiar heilt gjennom");
		System.out.println(lab1);
	}
}

class Labyrint{
	// Skal gå gjennom til nedre høgre hjørne
	// langs 1-tal
	//
	private static final int PRØVD = 3, STI = 7;
	private int[][] matrise;
	
	public Labyrint(){
		int mat[][] = { {1,1,1,0,1,1,0,0,0,1,1,1,1},
						{1,0,1,1,1,0,1,1,1,1,0,0,1}, 
						{0,0,0,0,1,0,1,0,1,0,1,0,0},
						{1,1,1,1,1,1,1,0,1,1,1,1,1} };
		matrise = mat;
	}
								
	public boolean gåGjennom(int rek, int kol){
		boolean ferdig = false;
		if (gyldig(rek,kol)){
			matrise[rek][kol]=PRØVD;
			if((rek==matrise.length-1)&&(kol==matrise[0].length-1))
				ferdig = true;	// nedre høgre hjørne
			else{
				ferdig = gåGjennom(rek+1, kol);		//Ned
				if(!ferdig)
					ferdig = gåGjennom(rek, kol+1);	//Høgre
				if(!ferdig)
					ferdig = gåGjennom(rek-1,kol);	//Opp	
				if(!ferdig)
					ferdig = gåGjennom(rek,kol-1);	//Venstre
			}
			if (ferdig)	// Denne posisjon er del av svaret
				matrise[rek][kol]=STI;
		}
		return ferdig;
	}
	
	private boolean gyldig(int r, int k){
		boolean svar = false;
		// Posisjonen må vera innafor matrisa og
		// ikkje prøvd før
		//
		if((r>=0)&&(r<matrise.length)&&(k>=0)&&(k<matrise[r].length))
			if(matrise[r][k]==1)
				svar = true;
				
		return svar;
	}
	
	public String toString(){
	// Heile matrisa som ein String over mange linjer
	//
		String svar = "\n";
		for(int r=0; r<matrise.length; r++){
			for(int k=0; k<matrise[r].length; k++)
				svar = svar + matrise[r][k]+"";
				
			svar = svar + "\n";
		}
		return svar;
	}
}